/**
 * Created by L.jp
 * Description:给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
 * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
 * 2.假设 nums[-1] = nums[n] = -−∞
 * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
 * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
 *
 * 如输入[2,4,1,2,7,8,4]时，会形成两个山峰，
 * 一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，
 * User: 86189
 * Date: 2022-05-25
 * Time: 11:22
 */
public class Solution {
    public static int findPeakElement (int[] nums) {
        //由于数组两边可视为最小值，所以使用二分法肯定可以找到峰值
        int left=0;
        int right= nums.length-1;
        while (left<right){
            int mid=(left+right)/2;
            if(nums[mid]>nums[mid+1]){
                //向右不一定能找到峰值,所以缩短右区间
                right=mid;
            }else{
                //向右肯定有峰值
                left=mid+1;
            }
        }
        //最后一次循环判断是区间内只有两个元素时，如果左边是7索引是3，右边时8索引是4，
        // 那么mid是3，所以mid<mid+1,此时就是进入到left=mid+1=right,所以在进入循环判断那会退出循环
        //此时right下标就是峰值下标
        return right;
    }
    
    public static void main(String[] args) {
        int[] nums={2,4,1,2,7,8,4};
        System.out.println(findPeakElement(nums));
    
    }
}
